1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuit layout, and more specifically to the art of placement of cells on integrated circuit chips.
2. Description of Related Art
Microelectronic integrated circuits (ICs) consist of a large number of electronic components which are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit (IC) transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in the various layers of the silicon chip.
The process of converting the specifications of an electrical circuit into a layout is called physical design. Physical design requires arranging elements, wires, and predefined cells on a fixed area, and the process can be tedious, time consuming, and prone to many errors due to tight tolerance requirements and the minuteness of the individual components, or cells.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. Feature size may be reduced to 0.1 micron within the next several years. The current small feature size allows fabrication of as many as 10 million transistors or approximately 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This feature-size-decrease/transistor-increase trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit. Larger chip sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design use extensively Computer Aided Design (CAD) tools. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The object of physical chip design is to determine an optimal arrangement of devices in a plane and to find an efficient interconnection or routing scheme between the devices that results in the desired functionality. Since space on the chip surface is at a premium, algorithms must use the space very efficiently to lower costs and improve yield. The arrangement of individual cells in an integrated circuit chip is known as a cell placement.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnection wire network, or net. A purpose of the optimization process used in the physical design stage is to determine a cell placement such that all of the required interconnections can be made, but total wirelength and interconnection congestion are minimized.
Typical methods for achieving this goal include generating one or more initial placements and modifying the placement or placements using optimization methodologies such as simulated annealing, genetic algorithms (i.e. simulated evolution), and force directed placement. Each of these techniques involve iterative applications of the respective algorithms to arrive at an estimate of the optimal arrangement of the cells.
Depending on the input, placement algorithms are classified into two major groups, constructive placement algorithms and iterative improvement algorithms. The input to the constructive placement algorithms consists of a set of blocks along with the netlist. The algorithm provides locations for the blocks. Iterative improvement algorithms start with an initial placement. These algorithms modify the initial placement in search of a better placement. The algorithms are applied in a recursive or an iterative manner until no further improvement is possible, or the solution is considered to be satisfactory based on certain predetermined criteria.
Iterative algorithms function by generating large numbers of possible placements and comparing them in accordance with some criteria which is generally referred to as fitness. The fitness of a placement can be measured in a number of different ways, for example, overall chip size. A small size is associated with a high fitness and a large size is associated with a low fitness. Another measure of fitness is the total wire length of the integrated circuit. A high total wire length indicates low fitness and a low total wire length, on the other hand, indicates high fitness. One cell placement optimization system is described in U.S. patent application Ser. No. 08/672,725. Applicants hereby incorporate the specification, including the drawings, of said application herein as though set forth in full.
The relative desirability of various placement configurations can alternatively be expressed in terms of cost, which can be considered as the inverse of fitness, with high cost corresponding to low fitness and, similarly, low cost corresponding to high fitness.
Iterative algorithms can generally be divided into three classifications: simulated annealing, simulated evolution and force directed placement. The simulated annealing algorithm simulates the annealing process that is used to temper metals. Simulated evolution simulates the biological process of evolution, while the force directed placement simulates a system of bodies attached by springs.
Assuming that a number N of cells are to be optimally arranged and routed on an integrated circuit chip, the number of different ways that the cells can be arranged on the chip, or the number of permutations, is equal to N| (N factorial). In the following description, each arrangement of cells will be referred to as a placement. In a practical integrated circuit chip, the number of cells can be hundreds of thousands or millions. Thus, the number of possible placements is extremely large.
Because of the large number of possible placements, computerized implementation of the placement algorithms discussed above can take many days. In addition, the placement algorithm may need to be repeated with different parameters or different initial arrangements to improve the results.
To reduce the time required to place optimally the cells, multiple processors have been used to speed up the process. In such implementations, multiple processors operate simultaneously to place optimally the cells on the integrated chip. However, such prior efforts to reduce the placement time by parallel processing of the placement methods have been impeded by three obstacles.
First, multiple processors may conflict with each other. This occurs where an area on the chip, which is being processed by one processor, is affected by movements of one or more cells into the area by another processor. When this occurs, one of the two conflicting processors must wait for the other to finish or postpone its own move for later. The area-conflict problem not only lessens the advantage of multiprocessing, but also increases the processing overhead encountered. This is because, before moving a cell, each of the processors must check for area-conflicts with all other processors. As the number of processors increases, the area-conflicts increase rapidly to negate the advantage of multiprocessing, such that the time required to place the cells is increased.
Second, the optimization process can become trapped in a local optimum. To eliminate the area-conflict problem, some systems have assigned particular core areas to each of the processors with the restriction that each of the processors only operate within its assigned area. After processing cells of the assigned areas, the processors are then assigned to different areas, and so on. Although this method eliminates area-conflicts, it limits the movements of the cells to the area assigned to the processor. The limitation on the movement of the cells increases the likelihood of the placement becoming stuck at a local optimum. In the case of a pairwise interchange algorithm, it is possible that a configuration achieved is at a local optimum such that any further exchange within the limited area will not result in a further reduction in cost. In such a situation, the algorithm is trapped at the local optimum and does not proceed further. This happens frequently when the algorithm is used in practical applications, and the extent of the local optimum problem increases as additional processors are added because the increase in the number of processors operating simultaneously reduces the area assigned to each of the processors. Decreases in the area assigned to each of the processors lead to corresponding decreases of the distances the cells of the areas may be moved to improve the optimization.
Third, if multiple processors are used simultaneously to place the cells of an integrated chip, it is possible for the processors to deadlock. This occurs where each of the processors has halted its operation while waiting for another processor to complete its operations. In this situation, all processing is stopped and the system halts. An example of deadlock is where processor P.sub.1 is waiting for processor P.sub.2 to complete its operation, P.sub.2 is waiting for processor P.sub.3 to complete its operation, and P.sub.3 is waiting for P.sub.1 to complete its operation. In that case, neither P.sub.1, P.sub.2, nor P.sub.3 will proceed.
In summary, because of the ever-increasing number of cells on an integrated chips (currently at millions of cells on a chip), and the resulting increase in the number of possible placements of the cells on the chip, a computer is used to find an optimal layout of the cells on the chip. Even with the aid of computers, existing methods can take several days to place a large number of cells, and these methods may need to be repeated with different parameters or different initial arrangements. To decrease the time required to place the chip, multiple processors have been used to perform the placement of the cells. However, the use of multiple processors has led to area-conflicts, local optimum problems, and potential deadlock situations, negating the advantages of using the multiple processors.